1. Field of the Invention
The present invention relates to the field of communications, and to an apparatus and method for congestion control in high speed networks. More particularly, the present invention relates to flow control techniques and the flow control of Available Bit Rate (ABR) traffic in, for example, Asynchronous Transfer Mode (ATM) networks.
2. Background and Material Information
With advanced ATM technologies, future high speed networks will be able to support a wide spectrum of applications with diverse traffic characteristics and service requirements. Using ATM Forum terminologies, traffic is classified into three classes: Constant Bit Rate (CBR), Variable Bit Rate (VBR) and Available Bit Rate (ABR). The CBR and VBR traffic are transmitted in high priority with sufficient reservation of buffer space and link capacity; their arrival rate is normally not adaptable to the changing network environment. In contrast, the ABR traffic is transmitted in low priority using the remaining buffer space and link capacity; their arrival rate is constantly ad justable to avoid network congestion. For low complexity high speed operation, the end to end flow control approach is found superior to that of link by link flow control. Further, the traditional window based flow control is no longer effective in high speed networks and is replaced by rate based control. In the rate based control design, the arrival rate of each ABR connection is dynamically adapted based on network feedback information.
A simple rate based control scheme uses single bit feedback information from the network. An example of such a control scheme is described in M. HLUCHYJ and N. YIN, xe2x80x9cOn Closed-loop Rate Control for ATM Networks,xe2x80x9d Proc. INFO-COM ""94, pp. 99-108 (1994), the disclosure of which is expressly incorporated herein by reference in its entirety. With single-bit feedback, a bit is marked at switching nodes or destination based on some preset congestion status. All the ABR sources will then adjust their transmission rate, based upon the single bit observation. An exemplary single-bit feedback scheme is called negative polarity feedback, and is described in J. C. BOLOT and A. SHANKAR, xe2x80x9cDynamic Behavior of Rate-based Flow Control Mechanisms,xe2x80x9d ACM Comp. Comm. Review, Vol. 20, No. 2, pp. 35-49 (1992), the disclosure of which is expressly incorporated herein by reference in its entirety. In negative polarity feedback, each ABR source reduces its transmission rate exponentially once receiving the negative feedback bit, otherwise each source keeps increasing its transmission rate linearly.
As indicated in the study described in R. JAIN et al., xe2x80x9cThe OSU Scheme for Congestion Avoidance Using Explicit Rate Indication,xe2x80x9d OSU Technical Report, September 1994, the disclosure of which is expressly incorporated herein by reference in its entirety, a single-bit rate based control is too slow to react to the rapidly changing traffic environment and an explicit rate control scheme should be designed to enhance control performance. One scheme was proposed by JAIN and his co-workers at Ohio State University. In the OSU scheme, a load factor is periodically computed at the congested node, the load factor being the ratio of present aggregate ABR rate to its desired rate. The rate of each individual ABR source in the next period is then simply equal to its current rate divided by the load factor. For example, if the aggregate rate is only one half of its desired rate, each source rate will be doubled in the next period.
The major advantage of most proposed single bit and explicit rate control schemes is their simplicity in implementation. However, to achieve such simplicity neither a dynamic control model nor round trip multiloop delays are considered in the above noted schemes. Yet, there is a price for simplicity which should be considered. First, most existing control schemes induce significant low frequency high magnitude oscillations in each feedback ABR control loop, where the oscillation frequency is directly associated with the round trip delay of each loop. It is intuitively clear that such inherent low frequency traffic oscillations will cause substantial oscillations in queuing process. As a result, a large buffer capacity has to be reserved at each node to absorb the ABR traffic oscillations. Second, the stability of the control schemes is highly sensitive to the high priority CBR/VBR traffic characteristics.
Another problem with most existing attempts on ABR feedback control design is they generally neglect the effect of multiple feedback loop delays and high priority traffic transmission. With multiloop delays, the already existing low frequency high magnitude oscillations of ABR traffic within each loop can become much worse. With high priority traffic transmission, the original control stability conditions can be ruined.
The closed loop stability problem is a major issue for any feedback control scheme. Its solution requires the knowledge of round trip delays of all ABR connections. In fact, the round trip delay is the main obstacle that prevents the prior systems from achieving good congestion control performance; especially within a wide area network, the round trip delay of individual ABR connections can be vastly different. For systems with multiple delays, their feedback controller must be carefully designed to provide closed loop stability, otherwise the systems can easily become unstable.
The study in L. BENMOHAMED and S. MEERKOV, xe2x80x9cFeedback Control of Congestion in Store-and-Forward Networks: The Described Case in Single Congestion Node,xe2x80x9d IEEE/ACM Trans. Networking, Vol. 1, No. 6, December 1993, pp. 693-708, the disclosure of which is expressly incorporated herein by reference in its entirety, considers round trip delays and analyzes the closed loop stability of an explicit rate control scheme in the absence of high priority traffic. In the disclosed scheme, a fluid flow queuing model is adopted and the queue size at the bottleneck node is used as the feedback information for the ABR traffic adaption. The feedback controller in BENMOHAMED et al. is designed only with the requirement of closed loop stability. No other performance criteria such as steady state error is considered.
In existing binary bit Available Bit Rate (ABR) congestion control schemes, nodal congestion is often detected by comparison of present queue size with a predetermined threshold. However, the queue threshold detection schemes have disadvantages. First, no congestion can be detected until the queue is longer than the threshold. Second, although the congestion is readily removed as the queue starts dropping, the detection of when the queue dropped below the threshold has unnecessarily extended the congestion period. The delayed detection followed by unnecessary extension of congestion periods significantly increases the oscillation period as well as the oscillation magnitude of ABR traffic within the network, causing a large consumption of buffer resources.
Therefore, despite the advances, congestion control of high speed network switches, such as ATM switches, is still inadequate. Large buffers are required to handle the overflow of data due to inaccurate detection of the network congestion. Moreover, multiple feedback loop delays and high priority traffic transmission has been neglected in existing feedback control designs. Thus, there exists a need for a system which accurately detects the congestion in an ATM network in order to optimize the throughput of ATM networks by controlling the flow of the ABR traffic.
In view of the foregoing, the present invention, through one or more of its various aspects, embodiments and/or specific features or subcomponents, is thus intended to bring about one or more of the objects and advantages as specifically noted below.
A general object of the present invention is to provide an apparatus and method for congestion control of high speed network switches, including ATM switches.
A further object of the invention is to provide a system which is capable of accurately detecting congestion of high speed network switches, such as ATM switches, in order to optimize the throughput of the network by controlling the flow of traffic.
According to an aspect of the invention, the link capacity requirement of CBR/VBR traffic is captured by its present filtered rate so that the ABR transmission rate will be periodically adapted to the remaining link capacity. However, because of multiloop delay and the CBR/VBR traffic variation, the link capacity will not be fully utilized. Another object of the present invention is therefore to minimize the unused link capacity. An advantage of the present invention is it eliminates unnecessary highly frequent adaptations of ABR traffic rate as found in most existing control schemes, which are caused either by the high frequency variation of CBR/VBR traffic or by the rapid change of queue congestion status. Because of the filtering, the ABR traffic varies very smoothly along with the slow time variation of the low frequency CBR/VBR traffic.
Another object of the invention is to provide an explicit rate ABR traffic control scheme by using a process control design method, referred to herein as Generated Prediction Control (GPC), to provide a closed loop stable controller with linear quadratic optimal performance. An advantage of the present invention is that multiloop delays of ABR connections are built into the design of the control model. The low frequency high magnitude oscillations of ABR traffic flow, as usually found in most proposed ABR control schemes, are therefore eliminated. As a result, not only is the buffer capacity requirement for ABR traffic substantially reduced, but the control stability condition is also significantly improved.
In a preferred embodiment, a new explicit rate control scheme based on the results of frequency domain analysis of multimedia traffic is provided. Examples of frequency domain analysis of multimedia traffic can be found in S. Q. LI and C. HWANG, xe2x80x9cQueue Response to Input Correlation Functions: Continuous Spectral Analysis,xe2x80x9d IEEE/ACM Trans, Networking, Vol. 1, No. 6, December 1993, pp. 678-692 (LI (I) et al. hereinafter), and S. Q. LI, S. CHONG, and C. HWANG, xe2x80x9cLink Capacity Allocation and Network Control by Filtered Input Rate in High Speed Networks,xe2x80x9d IEEE/ACM Trans. Networking, Vol. 3, No. 1, February 1995, pp. 10-15 (LI (II) et al. hereinafter), the disclosures of which are expressly incorporated herein by reference in their entireties. The inventors have found that the link capacity required by input traffic at each node is essentially captured by the traffic""s low frequency characteristics. In other words, no congestion occurs at the node if the control design guarantees that the aggregate CBR/VBR/ABR traffic rate, filtered in a low frequency band, never exceeds the link capacity. All the high frequency traffic is absorbed and smoothed out via limited buffering. Further, the filtered traffic rate is significantly less than its original non-filtered rate.
Another object of the present invention is to provide significant improvement of ABR traffic performance by replacing the queue threshold detection with the bandwidth threshold detection, using an Explicit Forward Congestion Indication (EFCI) scheme. According to an aspect of the invention, a modified EFCI scheme is provided, which is called EFCI-ECD) scheme, where ECD refers to early congestion detection. A simulation study has shown about a 60% savings in buffer capacity for the EFCI-ECD scheme to achieve the same throughput as the original EFCI scheme, providing the same set of source control parameters. The amplitude of the ABR traffic oscillation is reduced by about 50%. Note that the traffic filtering operation can easily by implemented by digital signal processing (DSP) chips. Using today""s technology, a common DSP chip only costs a few U.S. dollars whereas the high speed SRAM chips for buffer capacity are relatively much more expensive. Moreover, a single DSP chip can be shared by many links for multiple traffic measurement purposes.
Thus, there are at least three major advantages for the EFCI-ECD scheme of the present invention: (1) none of the existing EFCI protocols at source and destination needs to be changed; (2) the buffer capacity required at each switching node is substantially reduced; and (3) the ABR traffic oscillation is much reduced.
The present invention is described as a traffic congestion control apparatus for use in a network having a plurality of types of data traffic. The data traffic comprises high priority traffic and low priority traffic. The network has a plurality of links through which the data traffic flows, each link being susceptible to data traffic congestion. The apparatus has a processor which comprises a filter through which said data traffic flows, and a sampler which periodically measures a characteristic of the data traffic filtered by said filter. The measured characteristic indicates a present link capacity requirement of the filtered traffic. A flow control system for adjusting a flow rate of the low priority traffic is also provided. The apparatus also comprises a comparator which compares the measured characteristic with a predetermined threshold. The comparator sends a first signal to the flow control system when the measured characteristic exceeds the predetermined threshold to indicate link congestion. The comparator sends a second signal to the flow control system when the measured characteristic is below the predetermined threshold to indicate unused link capacity. The flow control system reduces the transmission rate of the low priority traffic in response to receipt of the first signal and increases the transmission rate of the low priority traffic in response to receipt of the second signal.
The traffic congestion control apparatus may be used in an asynchronous transfer method (ATM) network.
In a preferred embodiment, the filter is a low pass filter.
In another embodiment, a method for controlling congestion in a network is provided. The network has high priority data traffic and low priority data traffic, the low priority traffic being transmitted by a plurality of data inputs. The network comprises a plurality of links through which the data traffic flows. The method comprises filtering the data traffic and then periodically repeating the following steps: sampling the filtered traffic to estimate a present link capacity required by the high priority traffic; determining the remaining link capacity; calculating a transmission rate for each data input to minimize an unused link capacity of each link subject to no congestion; and adjusting a transmission flow rate of each data input to match the calculated transmission rate.
The above listed and other objects, features of advantages of the present invention will be more fully set forth below.